bitmap index
indexの手法の一つ
カスタマーを記述する次のようなテーブルを考える：
Customers(custid: integer, name: string, gender: boolean, rating:integer)
ratingの範囲は1 to 5、genderは2値
このように、値の取りうる可能性が少ないカラムはsparseという
アイデア
sparseなカラムに記録した値を、取りうる値ずつビット列として記録する
例
genderは2値なので2 bit使い、10か01と表現する
10 最初のビットの1はMale
01 2番目のビットの1はFemaleという意味
ratingの1は10000、5は00001と表現
一般化すると
カスタマーテーブルの全ての行のgenderの値は、2つのbitのベクターM,Fのコレクションとして扱うことができる
table: bit vectors
M F custid gender rating 1 2 3 4 5
1 0 112 M 3 0 0 1 0 0
1 0 115 M 5 0 0 0 0 1
0 1 119 F 5 0 0 0 0 1
1 0 122 M 4 0 0 0 1 0
左（M/F）・右（0-5）：bitmap index, 中央：カスタマーテーブル
1つめのベクトルはMaleを表し、2つ目のベクトルはFemaleを表す
どちらのbitベクトルもカスタマーテーブルの1行につき1bitを持つ
列に対するbitベクターのコレクションを、その列に対するbitmap indexと呼ぶ
上の表でいうとbitベクターM,Fの2つを合わせたものがそれ
ハッシュやツリーのインデックスに対するbitmap indexの2つの優位性
1. クエリへの解答に効率的なビット演算が利用できる
例
「レーティング5の男のカスタマーの数は？」のようなクエリに対して
genderのはじめのbit vector Mを取得し、ratingの5番目のvit bector5とANDのビット演算をすると、ratingが5の男のカスタマーの要素が1となるbit vectorが得られる
このbit vectorの1の数を数えればクエリへの解答になる